package com.unit2;

import java.util.Scanner;

/**
 * @author Toy
 * 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。
 * 例如:给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，
 * 或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。
 * 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
 * <p>
 * 思路： 1，分别用for循环嵌套
 */
public class Five {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int result = fun(money);
        if (result > 0) {
            System.out.println("方法一： 最少需要" + result + "个硬币。");
        }
        for (int i = money / 100; i >= 0; i--) {
            for (int j = money / 50; j >= 0; j--) {
                for (int k = money / 20; k >= 0; k--) {
                    for (int l = money / 10; l >= 0; l--) {
                        for (int m = money / 5; m >= 0; m--) {
                            for (int n = money / 2; n >= 0; n--) {
                                if (n * 2 + m * 5 + l * 10 + k * 20 + j * 50 + i * 100 == money) {
                                    System.out.println("方法二： 最少需要" + (i + j + k + l + m + n) + "个硬币");
                                    return;
                                }
                            }
                        }
                    }
                }
            }
        }
        System.out.println("方法二： 凑钱失败。");
    }

    private static int fun(int money) {
        int count = 0;
        count += money / 100;
        money = money % 100;
        count += money / 50;
        money = money % 50;
        count += money / 20;
        money = money % 20;
        count += money / 10;
        money = money % 10;
        count += money / 5;
        money = money % 5;
        count += money / 2;
        if (money %2 != 0) {
            System.out.println("方法一： 凑钱失败。");
            return -1;
        }
        return count;
    }
}
